\section{Heurística Constructiva}

\subsection{Introducción}
Una heurística constructiva es un algoritmo que intenta construir una instancia de algún problema complejo, como puede ser un problema de optimización combinatoria. El objetivo de esta sección es explicar la implementación de la heurística constructiva para el problema de \textbf{2-TSP}.\\

\subsection{Desarrollo}
La idea del algoritmo es ir construyendo una solución aproximada del problema, intentando que sea lo más óptima posible. De esta manera, se encara la resolución con una metodología ''golosa''  o "greedy". 
La construcción de la instancia del problema se realiza en dos pasos:\\

\begin{compactitem}
\item Sabemos que todos los nodos están relacionados entre sí, ya que el grafo es completo. En particular, el nodo \textbf{v} se relaciona con el resto de los demas nodos. El objetivo del primer paso es crear el punto inicial de la construcción, creando dos ciclos de tres nodos cada uno, con el nodo pivote \textbf{v} como único nodo común a los dos ciclos. Sabemos que podemos hacer esto, ya que el grafo tiene al menos 5 nodos. Se intenta elegir aquellos nodos cuyos ejes incidentes a \textbf{v} sean de peso mínimo. Sean $A, B, C, D$ los cuatro nodos adyacentes a \textbf{v} encontrados, se conecta $A$ a $B$ formando un ciclo, y $C$ a $D$ formando el segundo ciclo. De esta forma tenemos dos ciclos de tres nodos, los cuales servirán de punto de partida para el resto de la construcción de la solución.
\\
\item En el siguiente paso se insertan iterativamente el resto de los nodos que aún no hayan sido agregados a alguno de los ciclos, de la siguiente manera: dado un nodo a agregar, se calcula cual es el mejor lugar para ubicar dicho nodo entre dos nodos cualesquiera en alguno de los dos ciclos. Para esto se van precalculando todas las posibilidades, y se termina insertando en el lugar en el cual la inserción es óptima, ya que la suma de sus pesos es mínima. Esta operación es la que da la naturaleza golosa al algoritmo, ya que estamos suponiendo que esta política de inserción optimiza la construcción de la solución. Al ser una heurística, sabemos que esta suposición no necesariamente es correcta.\\



\end{compactitem}




\subsection{Pseudocódigo}
 El pseudocódigo del algoritmo está conformado por dos funciones principales:
 \textit{GenerateStartUpCycles} y \\ \textit{ConstructSolution}.\\
 
\begin{compactitem}
\item Como fue explicado en la sección anterior (Desarrollo), la primera parte del algoritmo construye dos ciclos de 3 nodos cada uno con el nodo protagonista \textit{v} como único nodo en común. Los nodos serán elegidos intentando unirlos a \textit{v} con el menor costo posible. La función \textit{GenerateStartUpCycles} se encarga de esta operación.\\

\item La tarea de la función \textit{ConstructSolution} consiste en ir agregando los nodos restantes, intentando insertar cada uno de ellos entre dos nodos ya pertenecientes a alguno de los dos ciclos, tambien de manera lo más óptima posible. Este procedimiento se realiza en las funciones \textbf{ConstructSolution} y \textbf{calculateInsertion} del código Java.\\

\end{compactitem}

Algunas variables para \textit{GenerateStartUpCycles}:\\

\begin{compactitem}
\item \textit{v}: Nodo pivote.
\item \textit{primerCiclo}: Se usa para guardar los elementos en uno de los ciclos.
\item \textit{segundoCiclo}: Se guardan los elementos restantes en el otro ciclo.
\item \textit{minSum}: Variable que se utiliza para almacenar la suma mínima de los ciclos.\\
\end{compactitem}


Algunas variables para \textit{ConstructSolution}:\\

\begin{compactitem}
\item \textit{solution}: Instancia en la cual se encuentran los dos ciclos a construir.
\item \textit{primerCiclo}: Se usa para guardar los elementos en uno de los ciclos.
\item \textit{segundoCiclo}: Se guardan los elementos restantes en el otro ciclo.
\item \textit{bestMinSum}: Variable que se utiliza para almacenar la suma mínima parcial al intentar insetar un nuevo nodo.
\item \textit{actualsum}: Variable auxiliar para guardar temporalmente cálculos de sumas.
\end{compactitem}

\newpage


\begin{algorithm}[H]
\caption{\operL{GenerateStartUpCycles}{\vin{input}{InstanceTP3}}{IntanceResultado}}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm


\FOR {cada uno de los nodos $i$ adyacentes a $v$}
	\STATE Guardar el costo del eje incidente a $v$ e $i$ asociado en la lista \textit{listIncidentes}.
\ENDFOR
%\STATE  Ordenar la lista de pesos \textit{listIncidentes} de menor a mayor.


\STATE  Obtenemos los 4 pesos menores \textit{weightA}, \textit{weightB}, \textit{weightC}, \textit{weightD} incidentes a \textit{v} de la lista \textit{listIncidentes}.\\

\STATE  Se obtienen los nodos asociados \textit{A}, \textit{B}, \textit{C} y \textit{D} , tal que se relacionan con \textit{v} por medio de los ejes \textit{weightA}, \textit{weightB}, \textit{weightC} y \textit{weightD}.  \\
\COMMENT Se calculan los costos entre los pares de nodos A y B, y tambien C y D.
\STATE edgeAB $\leftarrow $ costo del eje incidente a A y B.
\STATE edgeCD $\leftarrow $ costo del eje incidente a C y D.

\STATE  \COMMENT Se calcula el costo total de los dos ciclos formados.
\STATE  \textit{minSum} $\leftarrow $ $weightA + weightB + edgeAB + weightC + weightD + edgeCD$.


\STATE  Agregar nodo A a \textit{primerCiclo}.
\STATE  Agregar nodo B a \textit{primerCiclo}.
\STATE  Agregar nodo C a \textit{segundoCiclo}.
\STATE  Agregar nodo D a \textit{segundoCiclo}.
\STATE  \COMMENT La variable \textit{res} contiene a los ciclos construidos en esta función.
\STATE  Devolver \textit{res}.
\end{algorithmic}
Complejidades:

\begin{compactitem}
% 	\
	\item \textit{For} 1-3: Se recorren los $n-1$ ejes incidentes a $v$ y se los agrega a una lista. $O(n)$.
%\item Línea 4: Se ordena la lista con una operación de librería de Java. $O(n*log(n))$.		
\item Línea 4: Se obtienen los 4 costos mínimos de la lista. Esto implica recorrer una lista de tamaño \textit{n} buscando el mínimo, y luego volver a recorrerla para eliminar ese elemento. Esto es $2*O(n)$ por cada uno de los elementos. En total, $8*O(n)$.
\item Línea 5: Se obtienen los nodos asociados a los pesos, recorriendo la lista de nodos adyacentes a \textit{v}. $O(n)$.
\item Línea 6-7: Acceso a un elemento de la matriz que representa el grafo dentro de $Input$ y asignación, tiempos constantes. $O(1)$.
\item Línea 9: Suma y asignación de números enteros. $O(1)$.
\item Línea 10-13: Se agrega un elemento a la lista de enteros, en $O(1)$.
		
	\item \textbf{\underline{Complejidad Final}}: De los cálculos anteriores, podemos deducir que la complejidad temporal de GenerateStartUpCycles es de orden lineal, es decir $O(n)$.\\
\end{compactitem}
\end{algorithm}


\begin{algorithm}[H]
\caption{\operL{ConstructSolution}{\vin{solution}{InstanceResultado}}{IntanceResultado}}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm

\FOR {cada uno de los nodos $i$ que aún no fueron agregados}
	\STATE Marcar el nodo $i$ como agregado.
	\STATE \COMMENT Insertamos el nodo $i$ entre v y el primer elemento del primer ciclo.
	\STATE \COMMENT Asumimos como punto de partida que esta es la mejor inserción por ahora.
	\STATE \textit{bestAdjacentNodeA} $\leftarrow$ $v$;
	\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $first(primerCiclo)$;
	\STATE bestMinSum $\leftarrow$ minSum + peso($i$, $v$) + peso($i$,$first(primerCiclo)$) - peso($v$, $first(primerCiclo)$)
	
	\STATE \COMMENT Verificamos la inserción entre el nodo origen y último elemento del primer ciclo.
	\STATE actualSum $\leftarrow$ minSum + peso($i$, $v$) + peso($i$,$last(primerCiclo)$) - peso($v$, $last(primerCiclo)$)
	\IF	{$actualSum < bestMinSum$}				
		\STATE \textit{bestMinSum} $\leftarrow$ $actualSum$;
		\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $last(primerCiclo)$;
	\ENDIF
	\STATE \COMMENT Verificamos la inserción entre el nodo origen y primer elemento del segundo ciclo.
	\STATE actualSum $\leftarrow$ minSum + peso($i$, $v$) + peso($i$,$first(segundoCiclo)$) - peso($v$, $first(segundoCiclo)$)
	\IF	{$actualSum < bestMinSum$}				
		\STATE \textit{bestMinSum} $\leftarrow$ $actualSum$;
		\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $first(segundoCiclo)$;
	\ENDIF
	\STATE \COMMENT Verificamos la inserción entre el nodo origen y último elemento del segundo ciclo.
	\STATE actualSum $\leftarrow$ minSum + peso($i$, $v$) + peso($i$,$last(segundoCiclo)$) - peso($v$, $last(segundoCiclo)$)
	\IF	{$actualSum < bestMinSum$}				
		\STATE \textit{bestMinSum} $\leftarrow$ $actualSum$;
		\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $last(segundoCiclo)$;
	\ENDIF
	\STATE \COMMENT Se guarda la inserción óptima a medida que se va calculando.
	\STATE \COMMENT Se intenta insertar $i$ entre dos nodos cualesquiera intermedios del primer ciclo.
	\FOR {(cada uno de los ejes $e$ =($a,b$) del primer ciclo)}
		\STATE \textit{actualSum} $\leftarrow$ minSum
					+ peso($i$, $pos(a,primerCiclo)$)
					+ peso($i$, $pos(b, primerCiclo)$)
					- peso($pos(a,primerCiclo)$,$pos(b, primerCiclo)$)

	\IF	{$actualSum < bestMinSum$}				
		\STATE \textit{bestMinSum} $\leftarrow$ $actualSum$;
		\STATE \textit{bestAdjacentNodeA} $\leftarrow$ $a$;
		\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $b$;
	\ENDIF
	\ENDFOR
	
	\STATE \COMMENT Se intenta insertar $i$ entre dos nodos cualesquiera intermedios del segundo ciclo.
		\FOR {(cada uno de los ejes $e$ =($a,b$) del segundo ciclo)}
		\STATE \textit{actualSum} $\leftarrow$ minSum
					+ peso($i$, $pos(a,segundoCiclo)$)
					+ peso($i$, $pos(b, segundoCiclo)$)
					- peso($pos(a,segundoCiclo)$,$pos(b, segundoCiclo)$)

	\IF	{$actualSum < bestMinSum$}				
		\STATE \textit{bestMinSum} $\leftarrow$ $actualSum$;
		\STATE \textit{bestAdjacentNodeA} $\leftarrow$ $a$;
		\STATE \textit{bestAdjacentNodeB} $\leftarrow$ $b$;
	\ENDIF
	\ENDFOR
	\STATE \COMMENT Por último se actualiza el nuevo costo mínimo, y el estado de los ciclos.
	\STATE \textit{minSum} $\leftarrow$ $bestMinSum$;
	
\ENDFOR
\STATE \textit{res} $\leftarrow$ $realizarInsercionOptima$($bestAdjacentNodeA$, $bestAdjacentNodeB$)
\STATE  Devolver \textit{res}.
\end{algorithmic}
Complejidades:

\begin{compactitem}

\item Línea 1: Se recorren los nodos a agregar, como máximo $n$. Tenemos $n$ iteraciones del ciclo en el peor caso.		
\item Línea 5-7: Operaciones simples aritméticas o de asignacion. $O(1)$.
\item Línea 9-12/15-18/21-24: Operaciones simples aritméticas, de asignacion, y comprobación. $O(1)$.
%\item Línea 15-18: Operaciones simples aritméticas, de asignacion, y comprobación. $O(1)$.
%\item Línea 21-24: Operaciones simples aritméticas, de asignacion, y comprobación. $O(1)$.
\item Línea 28: La cantidad de ejes a iterar es proporcional a la cantidad de nodos en el ciclo. Acotable por $O(n)$.
\item Línea 29-33/38-42: Operaciones simples aritméticas, de asignacion, y comprobación. $O(1)$.
\item Línea 37: La cantidad de ejes a iterar es proporcional a la cantidad de nodos en el ciclo. Acotable por $O(n)$.
%\item Línea 38-42: Operaciones simples aritméticas, de asignacion, y comprobación. $O(1)$.
\item Línea 46: Operación de asignación. $O(1)$.
\item Línea 48: Costo de $realizarInsercionOptima$ es $O(n)$ en el peor caso (Ver abajo).
\item \textbf{\underline{Complejidad Final}}:: Tenemos un ciclo externo de ejecución cuyo bloque interno tiene un tiempo de ejecución lineal en función de $n$. Como el ciclo externo se ejecuta como máximo $n$ veces, podemos deducir que la complejidad de la funcion es $O(n^2)$.
\end{compactitem}

\end{algorithm}
\newpage


\begin{algorithm}[H]
\caption{\operL{realizarInsercionOptima}{\vin{bestAdjacentNodeA}{int}, \vin{bestAdjacentNodeB, \vin{i}{int}}{IntanceResultado}}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm

\STATE \COMMENT Si insertamos el nuevo nodo contiguo al nodo origen.
	\IF {$(bestAdjacentNodeA == v$)}	
		\IF {$existe$($primerCiclo, bestAdjacentNodeB$)}	
			\STATE \textit{index} $\leftarrow$ $indice$($primerCiclo$, $bestAdjacentNodeB$)
			\IF {$(index \neq 0)$}
				\STATE agregarAlFinal($primerCiclo$, $i$)
			\ELSE
				\STATE insertar($primerCiclo$, $i$)
			\ENDIF
		\ELSE
			\STATE \textit{index} $\leftarrow$ $indice$($segundoCiclo$, $bestAdjacentNodeB$)
			\IF {$(index \neq 0)$}
				\STATE agregarAlFinal($segundoCiclo$, $i$)
			\ELSE
				\STATE insertar($segundoCiclo$, $i$)
			\ENDIF
		
		\ENDIF
	\ELSE
	\STATE \COMMENT Si insertamos entre los nodos intermedios de alguno de los ciclos, no contiguo al nodo origen.		
		\IF {$existe$($primerCiclo, bestAdjacentNodeA$)}
			\STATE \textit{index} $\leftarrow$ $indice$($primerCiclo$, $bestAdjacentNodeA$)
			\STATE insertar($primerCiclo$, $index+1$, $i$)
		\ELSE
			\STATE \textit{index} $\leftarrow$ $indice$($segundoCiclo$, $bestAdjacentNodeA$)
			\STATE insertar($segundoCiclo$, $index+1$, $i$)
		\ENDIF
	\ENDIF



\STATE  Devolver \textit{res}.

\end{algorithmic}

\begin{compactitem}
\item Las operaciones \textit{existe}, \textit{indice}, \textit{insertar}, \textit{agregarAlFinal} de lista, cumplen su función en tiempo lineal $O(n)$. El resto de las operaciones son de asignación, comparación o aritméticas $O(1)$.
\item \textbf{\underline{Complejidad Final}}:: La complejidad total de $realizarInsercionOptima$  es de $O(n)$.


\end{compactitem}

\end{algorithm}





\newpage
\subsection{Complejidad}
La complejidad del algoritmo es cuadrática en función de la cantidad de nodos del grafo. Ya que $T_{Constructiva} =  T_{GenerateStartUpCycles} + T_{ConstructSolution} =  O(n) + O(n^2)$ = \textbf{$O(n^2)$}. El algoritmo debe verificar como máximo una cantidad proporcional a $n$ ejes para poder insertar un nodo en algún ciclo. Esto significa que por cada uno de los $n$ nodos, se debe calcular aproximadamente $n-1$ posibles inserciones.


\subsection{Demostración de la solución}

\subsubsection{Terminación}
El algoritmo termina porque en cada iteración del ciclo principal se elige un nuevo nodo aún no agregado a ninguno de los dos ciclos que están siendo construidos. En el momento de ser insertado un nodo en alguno de los ciclos, se marca este nodo como \textit{usado}. Se usa una estructura que mantiene el estado de los nodos, es decir, si ya fueron usados o no durante la construcción de la instancia solución.\\
En los ciclos internos del algoritmo, se recorren los nodos \textit{internos} pertenecientes a los ciclos, intentando insertar allí. Estos ciclos tambien terminan ya que están representados por listas finitas que representan a ciclos finitos simples.\\  


\subsubsection{Correctitud}
El algoritmo es correcto porque construye una solución correcta bajo las restricciones del enunciado:

\begin{compactitem}
\item Se generan dos ciclos que tienen en común un solo nodo \textit{v}, el nodo especificado por la instancia de entrada.
\item Ambos ciclos contienen a todos los nodos del grafo.
\item Los circuitos son simples, ya que no se repite inserciones del mismo nodo en ningún caso. Esto se asegura por el hecho de que todas las instancias recibidas son grafos con al menos 5 nodos, por ende los circuitos son simples y de al menos 3 vertices y 3 aristas.
\item El algoritmo no cumple la restricción de encontrar la mínima suma de los pesos de los ciclos, ya que en este caso, el algoritmo es una heurística aproximada golosa, que intenta aproximar en tiempo polinomial una solución lo suficientemente \textit{buena} aunque no óptima.

\end{compactitem}


\subsection{Tests}

Se decidió medir el costo de ejecución del algoritmo, por medio de una variable contadora de operaciones embebida en el código. Como se puede ver en el gráfico, la curva descripta por los resultados de las mediciones, muestran que puede ser acotada por una función cuadrática, eligiendo una constante conveniente. \\




\subsubsection{Test de Rendimiento}
\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestRendConst.png,width=0.9\linewidth,clip=}
\caption{Tests de Rendimiento para Algoritmo Constructivo para grafos completos aleatorios.}
\end{figure}

